Many real-world systems today rely on password authentication to verify the identity of a user before allowing that user to perform certain functions, such as setting up a virtual private network or downloading secret information. There are many security concerns associated with password authentication, due to the fact that the leakage of information to unscrupulous eavesdroppers can compromise the process, potentially resulting in drastic consequences.
When password authentication is performed over a network, one must be especially careful not to allow any leakage of information to one listening in, or even actively attacking, the network. Authentication over a network is an important part of security for systems that allow remote clients to access network servers, and is generally accomplished by verifying one or more of the following:
(i) something a user knows, e.g. a password;
(ii) something a user is, i.e., biometric information, such as a fingerprint; and
(iii) something a user has, i.e., some identification token, such as a smart-card.
For example, an automatic teller machine (ATM) verifies two of these: something a user has, the ATM card, and something a user knows, a personal identification number (PIN). ATM authentication is significantly easier than authentication over a data network because the ATM itself is considered trusted hardware, such that it is trusted to verify the presence of the ATM card and to transfer the correct information securely to a central transaction server.
In addition to authentication, key exchange is an important part of communication across a data network. Once a client and server have been authenticated, a secure communication channel must be set up between them. This is generally accomplished by the client and server exchanging a key, called a session key, for use during communication subsequent to authentication.
Authentication over a data network, especially a public data network like the Internet, is difficult because the communication between the client and server is susceptible to many different types of attacks. For example, in an eavesdropping attack, an adversary may learn secret information by intercepting communication between the client and the server. If the adversary learns password information, the adversary may replay that information to the server to impersonate the legitimate client in what is called a replay attack. Replay attacks are effective even if the password sent from the client is encrypted because the adversary does not need to know the actual password, but instead must provide something to the server that the server expects from the legitimate client (in this case, an encrypted password). Another type of attack is a spoofing attack, in which an adversary impersonates the server, so that the client believes that it is communicating with the legitimate server, but instead is actually communicating with the adversary. In such an attack, the client may provide sensitive information to the adversary.
Further, in any password-based authentication protocol, there exists the possibility that passwords will be weak such that they are susceptible to dictionary attacks. A dictionary attack is a brute force attack on a password that is performed by testing a large number of likely passwords (e.g., all the words in an English dictionary) against some known information about the desired password. The known information may be publicly available or may have been obtained by the adversary through one of the above-described techniques. Dictionary attacks are often effective because users often choose easily remembered, and easily guessed, passwords. Thus, a network authentication technique should have the following property with respect to an active attacker or adversary (i.e., one that may eavesdrop on, insert, delete, or modify messages on a network) who iteratively guesses passwords and runs the authentication protocol: the probability of such an attacker successfully impersonating a user is no better (or at most negligibly better) than it would be if the adversary engaged in a simple on-line guessing attack.
There are various known techniques for network authentication. Some of these techniques require the client to store the public key of the authentication server, including those where the protocol consists of sending a password over a previously secured web connection, such as is done in the well-known TLS Protocol standard (fully familiar to those of ordinary skill in the art), or in the Halevi-Krawczyk protocol, described in S. Halevi and H. Krawczyk, “Public-Key Cryptography and Password Protocols,” 5th ACM Conference on Computer and Communications Security, pp. 122–131, 1998, whose disclosure is incorporated by reference herein. (Note that the Halevi-Krawczyk protocol is provably secure against the type of attacker described above.)
Other techniques do not require the client to store a public key of the authentication server. These include, for example, those described in D. Jablon, Strong Password-Only Authenticated Key Exchange, ACM Computer Communication Review, ACM SIGCOMM, 26(5):5–20, 1996, and in T. Wu, The Secure Remote Password Protocol, 1998 Internet Society Symposium on Network and Distributed System Security, 1998, the disclosures of which are incorporated by reference herein. In addition, the following references also describe such protocols, and moreover, each of these protocols has been proven to be secure against the attacker described above: M. Bellare, D. Pointcheval, and P. Rogaway, Authenticated Key Exchange Secure Against Dictionary Attacks, Eurocrypt 2000, pp. 139–155, 2000 (hereinafter, “Bellare et al.”); commonly assigned U.S. patent application identified by Ser. No. 09/353,468, filed on Jul. 13, 1999 in the name of P. MacKenzie et al. and entitled “Secure Mutual Network Authentication Protocol (SNAPI)”; commonly assigned U.S. patent application identified by Ser. No. 09/638,320, filed on Aug. 14, 2000 in the name of V. V. Boyko et al. and entitled “Secure Mutual Network Authentication and Key Exchange Protocol”; commonly assigned U.S. patent application identified by Ser. No. 09/827,227, filed on Apr. 5, 2001 in the name of P. MacKenzie and entitled “Methods And Apparatus For Providing Efficient Password-Authenticated Key Exchange”; J. Katz, R. Ostrovsky and M. Yung, Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, Cryptology Eprint Archive, http:H/eprint.iacr.org/2001/031, 2001 (expanded version of J. Katz, R. Ostrovsky and M. Yung, Practical Password-Authenticated Key Exchange Provably Secure Under Standard Assumptions, Eurocrypt 2001, pp. 475–494, 2001); and O. Goldreich and Y. Lindell, Session-Key Generation Using Human Passwords Only, CRYPTO 2001, pp. 408–432, 2001. The disclosures of each of these references is also incorporated by reference herein.
However, all of these protocols, even the ones in which the server's public key is known to the user, are vulnerable to server compromise in the sense that compromising the server would allow an attacker to obtain the password verification data on that server (typically some type of one-way function of the password and some public values). This could then be used to perform an offline dictionary attack on the password. To address this issue (without resorting to assumptions such as, for example, tamper resistance), in W. Ford and B. S. Kaliski, Jr., Server-Assisted Generation of a Strong Secret from a Password, Proceedings of the 5th IEEE International Workshop on Enterprise Security, 2000 (hereinafter, “Ford and Kaliski”), the disclosure of which is incorporated by reference herein, it was suggested that the functionality of the server be distributed, thereby forcing an attacker to compromise multiple servers in order to be able to obtain password verification data. (As is well-known in the practice of distributed cryptography, for high security one should be careful to ensure that it is not easy for an attacker to compromise several servers with the same attack, which may be the case, for example, if they are all running the same operating system.) Note that the main problem in such an approach is not merely to distribute the password verification data, but to distribute the functionality, i.e., to distribute the password verification data such that it can be used for authentication without ever reconstructing the data on any one or more (but less than all) of the required servers.
While multiple party cryptosystems have been studied extensively (and many proven secure) for other cryptographic operations, such as signatures (see, e.g., Y. Desmedt and Y. Frankel, Threshold Cryptosystems, CRYPTO 1989, pp. 307–315, 1989, the disclosure of which is incorporated by reference herein), multi-server password-authenticated key exchange systems have no such history prior to the system disclosed in Ford and Kaliski. In D. Jablon, Password Authentication Using Multiple Servers, RSA Conference 2001, Cryptographers' Track, pp. 344–360, 2001 (hereinafter “Jablon”), the disclosure of which is also incorporated by reference herein, the system of Ford and Kaliski is extended, most notably so as not to require the server's public key to be known to the user.
However, neither the protocol of Ford and Kaliski nor the protocol of Jablon have been proven secure. Moreover, each of these prior art multi-server password authentication systems require the participation of each and every one of the servers in order to authenticate a client's password. While this makes it likely that the compromise of less than all of the servers will fail to compromise the client's password, it also fails to allow password authentication from taking place at all when any of the servers are unavailable (for whatever reason).